Theo Bát kỳ Mãn Châu thị tộc tông phổ, thủy tổ của Na Tô Đồ là Đoái Tề (兑齐), thuộc Tương Hoàng kỳ, là người đồng tộc với Mục Khắc Đàm Ba Đồ Lỗ (穆克谭巴图鲁), nhiều đời sống ở địa phương, thời kỳ đầu nhà Thanh lập quốc thì đến quy hàng. Ông nội Na Tô Đồ là Cát Lộc (噶禄), được tập thế chức Kỵ đô úy từ người chú Sắc Hách của mình, từng nhậm chức Thị vệ, Nội vụ phủ Chủ sự, Tổng quản Nội vụ phủ Đại thần. Theo Khâm định Bát kỳ thông chí, ông được Khang Hi đặc biệt ban cho đệ nhất thế quản Tá lĩnh đầu tiên của Mãn Châu Tương Hoàng kỳ đệ nhị Tham lĩnh.